package com.xaicode.algorithm.leetcode._101_200;

import java.util.Arrays;

/**
 * <a href="https://leetcode-cn.com/problems/rotate-array">旋转数组</a>
 *
 * <p>给定一个数组，将数组中的元素向右移动 <code>k</code><em> </em>个位置，其中 <code>k</code><em> </em>是非负数。</p>
 *
 * <p> </p>
 *
 * <p><strong>进阶：</strong></p>
 *
 * <ul>
 * 	<li>尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。</li>
 * 	<li>你可以使用空间复杂度为 O(1) 的 <strong>原地 </strong>算法解决这个问题吗？</li>
 * </ul>
 *
 * <p> </p>
 *
 * <p><strong>示例 1:</strong></p>
 *
 * <pre>
 * <strong>输入:</strong> nums = [1,2,3,4,5,6,7], k = 3
 * <strong>输出:</strong> <code>[5,6,7,1,2,3,4]</code>
 * <strong>解释:</strong>
 * 向右旋转 1 步: <code>[7,1,2,3,4,5,6]</code>
 * 向右旋转 2 步: <code>[6,7,1,2,3,4,5]
 * </code>向右旋转 3 步: <code>[5,6,7,1,2,3,4]</code>
 * </pre>
 *
 * <p><strong>示例 2:</strong></p>
 *
 * <pre>
 * <strong>输入：</strong>nums = [-1,-100,3,99], k = 2
 * <strong>输出：</strong>[3,99,-1,-100]
 * <strong>解释:</strong>
 * 向右旋转 1 步: [99,-1,-100,3]
 * 向右旋转 2 步: [3,99,-1,-100]</pre>
 *
 * <p> </p>
 *
 * <p><strong>提示：</strong></p>
 *
 * <ul>
 * 	<li><code>1 <= nums.length <= 2 * 10<sup>4</sup></code></li>
 * 	<li><code>-2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1</code></li>
 * 	<li><code>0 <= k <= 10<sup>5</sup></code></li>
 * </ul>
 *
 * @author beborn xaicode@sina.com
 */
public class _189_Medium_RotateArray {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7};
        int k = 3;
        _189_Medium_RotateArray rotateArray = new _189_Medium_RotateArray();

        rotateArray.rotate(arr, k);
    }

    /**
     * 使用额外的数组
     * <p>
     * 执行耗时:1 ms,击败了66.35% 的Java用户
     * 内存消耗:55.2 MB,击败了58.43% 的Java用户
     */
    public void rotate(int[] nums, int k) {
        System.out.printf("original array %s\n", Arrays.toString(nums));
        System.out.printf("rotate %d times\n", k);
        int n = nums.length;
        int[] newArr = new int[n];
        for (int i = 0; i < n; ++i) {
            newArr[(i + k) % n] = nums[i];
        }
        System.arraycopy(newArr, 0, nums, 0, n);

        System.out.printf("new array is %s", Arrays.toString(newArr));
    }

    /**
     * 环状替换
     * <p>
     * 执行耗时:2 ms,击败了27.91% 的Java用户
     * 内存消耗:55.3 MB,击败了57.79% 的Java用户
     */
    public void rotate2(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int count = gcd(k, n);
        for (int start = 0; start < count; ++start) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
            } while (start != current);
        }
    }

    public int gcd(int x, int y) {
        return y > 0 ? gcd(y, x % y) : x;
    }

    /**
     * 数组翻转
     * <p>
     * 执行耗时:0 ms,击败了100.00% 的Java用户
     * 内存消耗:55.3 MB,击败了57.15% 的Java用户
     */
    public void rotate3(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }
    }

}
